package com.example.daiyinuo.leetcode;

/**
 * 给你一个整数数组nums和一个整数target 。
 * 向数组中的每个整数前添加'+'或' - '，然后串联起所有整数，可以构造一个表达式：
 * 例 如 ， nums=[2,1] ， 可 以 在 2 之 前 添 加 '+' ， 在 1 之 前 添 加 ' - ' ，
 * 然 后 串 联 起 来 得 到 表 达 式"+2-1"。
 * 返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。
 */
public class leetCode494 {
    public static int result(int [] nums,int target){
        int length = nums.length;
        int sum = 0;
        for (int num:nums)
            sum+=num;
        //如果所有数字的和小于target 或者sum-target是奇数
        //无论怎么添加符号，表达式都不可能成立
        if(sum<target ||((sum -target)&1) !=0){
            return 0;
        }
        //我们要找到一些元素让他们的和等于capacity的方案数即可
        int capacity = (sum - target)>>1;
        //dp[i][j]表示在数nums的前i元素中选择一些元素，让他们的结果等于j的方案数
        int dp[][] = new int[length+1][capacity+1];
        //边界条件
        dp[0][0] = 1;
        for(int i=1;i<=length;i++){
            for(int j=0;j<=capacity;j++){
                //下面是地推公式
                if(j>=nums[i-1]){//不选第i个和选第i个元素
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];

                }else{
                    dp[i][j] = dp[i-1][j];
                }
                System.out.println("i==="+i+",j=="+j+",dp[i][j]=="+dp[i][j]);
            }
        }

        return dp[length][capacity];
    }
    public static int findTargetSumWays(int []nums,int target){
        int length = nums.length;
        int sum =0;
        for (int num:nums)
            sum += num;
        if(sum <target || ((sum-target)&1) != 0){
            return 0;
        }
        int capacity = (sum - target)>>1;
        int dp[] = new int[capacity+1];
        //边界条件
        dp[0] = 1;
        for(int i=1;i<=length;i++){
            for(int j=capacity;j>=0;j--){
                if(j>=nums[i-1]){
                    dp[j] += dp[j-nums[i-1]];
                }
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int arr[] = {1,1,1,1,1};
        System.out.println("result=="+findTargetSumWays(arr,3));
    }
}
